
// ===============================================================================================================
// -*- C++ -*-
//
// MeshOptimize.cpp - Progressive Mesh implementation, based on the algorithms presented here:
// http://www.melax.com/polychop - By Stan Melax.
//
// Copyright (c) 2010 Guilherme R. Lampert
// guilherme.ronaldo.lampert@gmail.com
//
// This code is licenced under the MIT license.
//
// This software is provided "as is" without express or implied
// warranties. You may freely copy and compile this source into
// applications you distribute provided that the copyright text
// above is included in the resulting source code.
//
// ===============================================================================================================

#include "MeshOptimize.hpp"

// FIXME: This static variables could become a serious problem
// if someone decides to call MeshOptimize() in a multithreaded app.
// So do not use this code on parallel applications before fixing this issue.

// ==== Local Variables ================
static vertex_list_t g_vertices;
static triangle_list_t g_triangles;
// =====================================

// == Extended Triangle Class ==

TriangleEx::TriangleEx()
{
	vertex[0] = 0;
	vertex[1] = 0;
	vertex[2] = 0;
}

TriangleEx::TriangleEx(VertexEx * v0, VertexEx * v1, VertexEx * v2)
{
	vertex[0] = v0;
	vertex[1] = v1;
	vertex[2] = v2;

	computeNormal();

	for (int i = 0; i < 3; i++)
	{
		vertex[i]->adjacent_tris.push_back(this);

		for (int j = 0; j < 3; j++)
		{
			if (i != j)
			{
				vertex[i]->adjacent_verts.add_unique(vertex[j]);
			}
		}
	}
}

void TriangleEx::computeNormal()
{
	const Vec3 & v0 = vertex[0]->pos;
	const Vec3 & v1 = vertex[1]->pos;
	const Vec3 & v2 = vertex[2]->pos;

	normal = (v1-v0).CrossProduct(v2-v1);
	normal.Normalize();
}

void TriangleEx::replaceVertex(VertexEx * vOld, VertexEx * vNew)
{
	if (vOld == vertex[0])
	{
		vertex[0] = vNew;
	}
	else if (vOld == vertex[1])
	{
		vertex[1] = vNew;
	}
	else
	{
		vertex[2] = vNew;
	}

	int i, j;

	vOld->adjacent_tris.remove(this);
	vNew->adjacent_tris.push_back(this);

	for (i = 0; i < 3; i++)
	{
		vOld->removeIfNonNeighbor(vertex[i]);
		vertex[i]->removeIfNonNeighbor(vOld);
	}

	for (i = 0; i < 3; i++)
	{
		for (j = 0; j < 3; j++)
		{
			if (i != j)
			{
				vertex[i]->adjacent_verts.add_unique(vertex[j]);
			}
		}
	}

	computeNormal();
}

bool TriangleEx::hasVertex(const VertexEx * v) const
{
	return ((v == vertex[0]) || (v == vertex[1]) || (v == vertex[2]));
}

TriangleEx::~TriangleEx()
{
	int i;

	g_triangles.remove(this);

	for (i = 0; i < 3; i++)
	{
		if (vertex[i])
			vertex[i]->adjacent_tris.remove(this);
	}

	for (i = 0; i < 3; i++)
	{
		int j = (i+1)%3;

		if (!vertex[i] || !vertex[j])
			continue;

		vertex[i]->removeIfNonNeighbor(vertex[j]);
		vertex[j]->removeIfNonNeighbor(vertex[i]);
	}
}

// == Extended Vertex Class ==

void VertexEx::removeIfNonNeighbor(VertexEx * v)
{
	if (adjacent_verts.contains(v))
	{
		unsigned int i = adjacent_tris.size();

		while (i--)
		{
			if (adjacent_tris[i]->hasVertex(v))
				return;
		}

		adjacent_verts.remove(v);
	}
}

VertexEx::~VertexEx()
{
	while (adjacent_verts.size())
	{
		adjacent_verts[0]->adjacent_verts.remove(this);
		adjacent_verts.remove(adjacent_verts[0]);
	}

	g_vertices.remove(this);
}

// == Mesh Optimization Code ==

static float ComputeEdgeCollapseCost(const VertexEx * u, const VertexEx * v)
{
	float edgelength = (u->pos - v->pos).Length();
	float curvature = 0.0f;

	unsigned int i, nTris = u->adjacent_tris.size();

	triangle_list_t sides;

	for (i = 0; i < nTris; i++)
	{
		if (u->adjacent_tris[i]->hasVertex(v))
		{
			sides.push_back(u->adjacent_tris[i]);
		}
	}

	unsigned int j, nSides = sides.size();

	for (i = 0; i < nTris; i++)
	{
		float mincurv = 1.0f;

		for (j = 0; j < nSides; j++)
		{
			float dot = u->adjacent_tris[i]->normal.DotProduct(sides[j]->normal);

			mincurv = MIN(mincurv, (1.0f - dot) / 2.0f);
		}

		curvature = MAX(curvature, mincurv);
	}

	return (edgelength * curvature);
}

static void ComputeEdgeCostAtVertex(VertexEx * v)
{
	if (v->adjacent_verts.size() == 0)
	{
		// 'v' Doesn't have neighbors so it costs nothing to collapse.
		v->collapse = 0;
		v->objdist = -0.01f;
		return;
	}

	v->objdist = 1000000;
	v->collapse = 0;

	// Search all neighboring edges for the least cost edge:
	unsigned int i = v->adjacent_verts.size();

	while (i--)
	{
		float dist = ComputeEdgeCollapseCost(v, v->adjacent_verts[i]);

		if (dist < v->objdist)
		{
			v->collapse = v->adjacent_verts[i];	// Candidate for edge collapse.
			v->objdist = dist;					// Cost of the collapse.
		}
	}
}

static void ComputeAllEdgeCollapseCosts()
{
	// For all the edges, compute the difference it would make
	// to the model if it was collapsed. the least of these per
	// vertex is cached in each vertex object.

	unsigned int i = g_vertices.size();

	while (i--)
	{
		ComputeEdgeCostAtVertex(g_vertices[i]);
	}
}

static void Collapse(VertexEx * u, VertexEx * v)
{
	// Collapse the edge u|v by moving vertex u onto v.
	// Actually remove triangles on u|v, then update triangles
	// that have u to have v, and remove u.

	if (v == 0)
	{
		// u is a vertex all by itself, so just delete it.
		if (u != 0)
		{
			delete u;
		}
		return;
	}

	// Make a temp copy of u adjacent vertices:

	unsigned int i, nVerts = u->adjacent_verts.size();

	vertex_list_t tmp_verts;
	tmp_verts.resize(nVerts);

	for (i = 0; i < nVerts; i++)
	{
		tmp_verts[i] = u->adjacent_verts[i];
	}

	// Delete triangles on the edge u|v:

	i = u->adjacent_tris.size();

	while (i--)
	{
		TriangleEx * pTri = u->adjacent_tris[i];

		if (pTri->hasVertex(v))
			delete pTri;
	}

	// Update remaining triangles to have v instead of u:

	i = u->adjacent_tris.size();

	while (i--)
	{
		u->adjacent_tris[i]->replaceVertex(u, v);
	}

	delete u;

	// Recompute the edge collapse costs for neighboring vertices:

	for (i = 0; i < nVerts; i++)
	{
		ComputeEdgeCostAtVertex(tmp_verts[i]);
	}
}

static VertexEx * MinimumCostEdge()
{
	// Find the edge that when collapsed will affect the model the least.

	VertexEx * v = g_vertices[0];

	unsigned int i = g_vertices.size();

	while (i--)
	{
		if (g_vertices[i]->objdist < v->objdist)
		{
			v = g_vertices[i];
		}
	}

	return (v);
}

void MeshOptimize(const Array<Vec3> & vertices, const Array<Triangle> & indices, Array<int> & Map, Array<int> & Permutation)
{
	// The caller of this function should reorder their vertices according to the output parameter 'Permutation'.
	// Memory allocated done here is released in the 'Collapse()' routine.

	unsigned int i, size;

	size = vertices.size();
	g_vertices.resize(size);

	for (i = 0; i < size; i++)
	{
		g_vertices[i] = new VertexEx(vertices[i], i);
	}

	size = indices.size();
	g_triangles.resize(size);

	for (i = 0; i < size; i++)
	{
		g_triangles[i] = new TriangleEx(g_vertices[indices[i].VertexIndex[0]],
										g_vertices[indices[i].VertexIndex[1]],
										g_vertices[indices[i].VertexIndex[2]]);
	}

	ComputeAllEdgeCollapseCosts();

	Permutation.resize(g_vertices.size());
	Map.resize(g_vertices.size());

	// Reduce the object down to nothing:
	while (g_vertices.size() > 0)
	{
		// Get the next vertex to collapse:
		VertexEx * v = MinimumCostEdge();

		// Keep track of this vertex, i.e. The collapse ordering:
		Permutation[v->id] = g_vertices.size()-1;

		// Keep track of the vertex to which we collapse to:
		Map[g_vertices.size()-1] = ((v->collapse) ? v->collapse->id : -1);

		// Collapse this edge:
		Collapse(v, v->collapse);
	}

	const unsigned int mapSize = Map.size();

	for (i = 0; i < mapSize; i++)
	{
		Map[i] = ((Map[i] == -1) ? 0 : Permutation[Map[i]]);
	}

	g_triangles.clear();
	g_vertices.clear();
}
